package com.lx.algorithm.code;

/**
 * Description:
 * Copyright:   Copyright (c)2019
 * Company:     zefu
 *
 * @author: 张李鑫
 * @version: 1.0
 * Create at:   2021-12-30 00:06:42
 * <p>
 * Modification History:
 * Date         Author      Version     Description
 * ------------------------------------------------------------------
 * 2021-12-30     张李鑫                     1.0         1.0 Version
 */
public class Code02 {
    /**
     * 括号有效配对是指：
     * 1）任何一个左括号都能找到和其正确配对的右括号
     * 2）任何一个右括号都能找到和其正确配对的左括号
     * 有效的：    (())  ()()   (()())  等
     * 无效的：     (()   )(     等
     * 问题一：怎么判断一个括号字符串有效？
     * 问题二：如果一个括号字符串无效，返回至少填几个字符能让其整体有效
     */

    public static boolean valid(String s) {
        if (s == null || s.length() < 2) {
            return false;
        }
        char[] chars = s.toCharArray();
        int count = 0;
        for (int i = 0; i < chars.length; i++) {
            if (count < 0) {
                return false;
            }

            if (chars[i] == '(') {
                count++;
            } else if (chars[i]==')'){

                count--;
            }
        }
        return count == 0;
    }

    public static int needParent(String s) {
        if (s == null || s.length() < 2) {
            return 0;
        }
        char[] chars = s.toCharArray();
        int need=0;
        int count = 0;
        for (int i = 0; i < chars.length; i++) {

            if (chars[i] == '(') {
                count++;
            } else  {
                //这里必须用need变量 ))))((((这样的count是0但是其实他要补double的值
                if (count==0){
                    need++;
                }else {
                    count--;
                }

            }
        }
        return count+count;
    }


    public static int needParentheses(String s) {
        char[] str = s.toCharArray();
        int count = 0;
        int need = 0;
        for (int i = 0; i < str.length; i++) {
            if (str[i] == '(') {
                count++;
            } else { // 遇到的是')'
                if (count == 0) {
                    need++;
                } else {
                    count--;
                }
            }
        }
        return count + need;
    }



    public static void main(String[] args) {
        String str="(()()())(((((";
        System.out.println(needParentheses(str));
        System.out.println(needParent(str));
    }
}